/**
 * @version: V1.0
 * @Title: CustomHeap.java
 * @Description:
 * @author wangshipeng
 * @date 2022-01-12 22:15
 * @Copyright: 2022-01-12
 */

package com.peng.heap;

import com.peng.old.util.SortUtil;

/**
 * @author wangshipeng
 * @ClassName: CustomHeap
 * @Description:
 * @date 2022-01-12 22:15
 */
public class HeapSort {


    public HeapSort(int[] arr) {
//        for (int i = 0; i < arr.length; i++) {
//            heapInsert(arr, i);
//        }
        int heapSize = arr.length;
        for (int i = arr.length - 1; i >= 0; i--) {
            heapify(arr, i, heapSize);
        }
//
//        System.out.println(arr);
        while (heapSize > 0) {
            swap(arr, 0, --heapSize);
            heapify(arr, 0, heapSize);
        }


    }

    public static void main(String[] args) {


        for (int i = 0; i < 5000; i++) {
            int[] ints = SortUtil.makeRandomArray(100);
            HeapSort heapSort = new HeapSort(ints);
            if (!SortUtil.checkResult(ints)) {
                System.out.println("oops!!");
            }
        }
    }

    /*

      4
    6  9
 6  1 2

     */

    private void heapInsert(int[] originArr, int index) {
        while (originArr[index] > originArr[(index - 1) / 2]) {
            swap(originArr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    private void heapify(int[] originArr, int index, int heapSize) {
        int left = (index << 1) + 1;
        while (left < heapSize) {
            int right = left + 1;
            int pos = right < heapSize && originArr[right] > originArr[left] ? right : left;
            int choosePos = originArr[index] < originArr[pos] ? pos : index;
            if (choosePos == index) {
                break;
            }
            swap(originArr, index, choosePos);

            index = choosePos;

            left = (index << 1) + 1;
        }


    }

    private void swap(int[] originArr, int i, int j) {
        if (i == j) {
            return;
        }
        int temp = originArr[i];
        originArr[i] = originArr[j];
        originArr[j] = temp;
    }


}
